"""
归并排序
"""


def merge_sort(array):
    # 递归结束条件
    if len(array) <= 1:
        return
    
    # 划分
    middle_point = len(array) // 2
    left_part = array[:middle_point] # 左半部分
    right_part = array[middle_point:] # 右半部分

    # 对子问题继续划分
    merge_sort(left_part)
    merge_sort(right_part)

    # 子问题经过合并之后，左右两部分都已经有序
    left_array_index = 0 # 左半部分索引
    right_array_index = 0 # 右半部分索引
    sorted_index = 0 # 排序索引

    while left_array_index < len(left_part) and right_array_index < len(right_part):
        # 左右两部分依次比较，将较小的元素放入排好序的列表中，同时移动索引
        if left_part[left_array_index] < right_part[right_array_index]:
            array[sorted_index] = left_part[left_array_index]
            left_array_index += 1
        else:
            array[sorted_index] = right_part[right_array_index]
            right_array_index += 1
        sorted_index += 1

    # 处理左右两侧列表长度不相等的情形
    while left_array_index < len(left_part):
        array[sorted_index] = left_part[left_array_index]
        left_array_index += 1
        sorted_index += 1
    
    while right_array_index < len(right_part):
        array[sorted_index] = right_part[right_array_index]
        right_array_index += 1
        sorted_index += 1


if __name__ == '__main__':
    numbers = [4, 10, 6, 14, 2, 1, 8, 5]
    print('Unsorted array: ')
    print(numbers)
    merge_sort(numbers)
    print('Sorted array: ')
    print(numbers)